#ifndef __HASHMAP_HPP_
#define __HASHMAP_HPP_

#include <string>
#include<iostream>
template<typename T>
class HashMap //键值对
{
public: 
    HashMap(const int & size);
    ~HashMap();
    void Insert(const std::string& key,const T& value);
    void Remove(const std::string& key);

    T* GetByKey(const std::string& key);

    T& operator[](const std::string& key);
    void show();
    void showByGroup();

    template<typename U>
    friend std::ostream &operator<<(std::ostream &os,HashMap<U>& h);

private:
    struct Node //节点
    {
        Node(const std::string& key,const T& value):key(key),value(value),next(nullptr){}
        std::string key; //键
        T value; //值
        Node *next; //指向下一个节点的指针
    };
    Node* *array; //数组指针
    const int size; //数组大小
    //哈希函数
    int Hash(const std::string& key);
};


template<typename T>
HashMap<T>::HashMap(const int &size):size(size)
{
    array = new Node*[size];
    for(int i = 0;i < size;i++)
        array[i] = nullptr;
}

template <typename T>
inline HashMap<T>::~HashMap()
{
    for(int i = 0;i < size;i++)
    {
        if(array[i])
            delete array[i];
    }
    delete []array;
}

template<typename T>
void HashMap<T>::Insert(const std::string &key, const T &value)
{
    Node *node = new Node(key,value);
    //计算哈希值
    int index = Hash(key);
    node->next = array[index];
    array[index] = node;
}

template<typename T>
void HashMap<T>::Remove(const std::string &key)
{
    Node *node = array[Hash(key)];
    if(node == nullptr)
        return;
    if(node->key == key)
    {
        array[Hash(key)] = node->next;
        delete node;
        return;
    }
    else
    {
        Node *travelPoint = node;
        while(travelPoint->next)
        {
            if(travelPoint->next->key == key)
            {
                Node *freeNode = travelPoint->next;
                travelPoint->next = freeNode->next;
                delete freeNode;
                return;
            }
        }
        travelPoint = travelPoint->next;
    }
}

template<typename T>
T *HashMap<T>::GetByKey(const std::string &key)
{
    Node *node = array[Hash(key)];
    while(node)
    {
        if(node->key == key)
        {
            return &node->value;
        }
        node = node->next;
    }
    return nullptr;
}

template<typename T>
T &HashMap<T>::operator[](const std::string &key)
{
    T *data = GetByKey(key);
    //存在就返回
    if(data)
        return *data;
    //不存在就创建
    else
    {
        Insert(key,T());
        return *GetByKey(key);
    }
}

template<typename T>
void HashMap<T>::show()
{
    for(int i = 0;i < size;i++)
    {
        Node *travelPoint = array[i];
        while(travelPoint != nullptr)
        {
            std::cout<<"hash值:"<<i<<" "
                     <<"key : "<<travelPoint->key<<" "
                     <<"value : "<<travelPoint->value;
            std::cout<<std::endl;
            travelPoint = travelPoint->next;

        }
    }
}

template<typename T>
void HashMap<T>::showByGroup()
{
    for(int i = 0;i < size;i++)
    {
        Node *travelPoint = array[i];
        if(travelPoint == nullptr)
            continue;
        while(travelPoint != nullptr)
        {
            std::cout<<travelPoint->value <<" ";
            travelPoint = travelPoint->next;
        }
         std::cout<<std::endl;
    }
}

template<typename T>
int HashMap<T>::Hash(const std::string &key)
{
    //字符串到整型数据的映射
    int hash = 0;
    for(int i = 0;i < key.size();i++)
    {
        hash = (hash *31 + key[i]) % size;
    }
    return hash;
}


template <typename U>
inline std::ostream &operator<<(std::ostream &os, HashMap<U> &h)
{
    for(int i = 0;i < h.size;i++)
    {
        typename HashMap<U>::Node *travelPoint = h.array[i];
        while(travelPoint != nullptr)
        {
            std::cout<<"hash值:"<<i<<" "
                     <<"key : "<<travelPoint->key<<" "
                     <<"value : "<<travelPoint->value;
            std::cout<<std::endl;
            travelPoint = travelPoint->next;

        }
    }
    return os;
}

#endif